package com.ljy.my_study.lintcode.判断链表有环;

import com.ljy.my_study.lintcode.翻转链表.TestMain.ListNode;

/** 
* @author James
* @date 2018年9月28日 
*/
public class TestMain {
	public static void main(String[] args) {
		int[] nums= {1,2,3,4,5,6,7,8,9,10};
		ListNode head=createRingListNode(nums,4);
		ListNode missedNode=isHasRing(head);
		ListNode ringPoint=intoRingNode(head,missedNode);
	}
	//不断循环，分出两个记步，一个快，一个慢，快比慢每次多走一步。
	//当n次循环后，快步和慢步相遇。记n次循环，起点到入环点之间p步，从入环点到相遇点之间c步，
	//则n=p+c,快步走了2*n，比慢步多了n。多出来的n步则是绕着相遇点走一圈的步数。
	//所以从起始点到入环点步数，和相遇点到入环点步数是一样的。
	private static ListNode createRingListNode(int[] nums,int index) {
		ListNode head=null;
		ListNode nowNode=null;
		ListNode ringPoint=null;
		for(int i=0;i<nums.length-1;i++) {
			if(i==0) {
				nowNode=new ListNode(nums[i]);
				head=nowNode;
			}
			if(index==i) {
				ringPoint=nowNode;
			}
			nowNode.next=new ListNode(nums[i+1]);
			nowNode=nowNode.next;
			if(i==nums.length-2) {
				nowNode.next=ringPoint;
			}
		}
		return head;
	}
	
	//判断一个链表是否有环
	public static ListNode isHasRing(ListNode head) {
		ListNode one=head;
		ListNode two=head;
		while(true) {
			if(!(one==null||two==null)) {
				one=one.next;
				two=two.next;
				if(two!=null)two=two.next;
				else return null;
				if(one==two) {
					return one;
				}
			}else {
				return null;
			}
		}
	}
	
	//获取一个有环链表中入环点
	public static ListNode intoRingNode(ListNode head,ListNode missedNode) {
		while(head!=missedNode) {
			head=head.next;
			missedNode=missedNode.next;
		}
		return head;
	}
	
	public static class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}

		@Override
		public String toString() {
			return "{\"val\":\"" + val + "\",\"next\":\"" + next + "\"} ";
		}
		
	}
}
